#define _CRT_SECURE_NO_WARNINGS 1

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *left;
 *     struct Node *right;
 *     struct Node *next;
 * };
 */

void Left_Right(struct Node* root)
{
    if (root->left == NULL)
        return;
    root->left->next = root->right;
    Left_Right(root->left);
    Left_Right(root->right);
}

void Right_Left(struct Node* left, struct Node* right)
{
    if (left->left == NULL)
        return;
    left->right->next = right->left;
    Right_Left(left->left, left->right);
    Right_Left(left->right, right->left);
    Right_Left(right->left, right->right);
}

struct Node* connect(struct Node* root) {
    if (root == NULL || root->left == NULL)
        return root;
    Left_Right(root);
    Right_Left(root->left, root->right);
    return root;
}